/**
 * 
 */
package com.module.hq.graph;

import java.util.ArrayList;
import java.util.Collections;

import com.dalonedrau.graph.DijkstraComparator;
import com.dalonedrau.graph.DijkstraSearchImpl;
import com.dalonedrau.graph.IndexedPriorityQLow;
import com.dalonedrau.graph.SparseGraph;
import com.dalonedrau.graph.WeightedGraphEdge;

/**
 * @author Donald
 */
public class HQGraphSearchDijkstra implements DijkstraSearchImpl {	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public float[] getDistances() {
		return costToThisNode;
	}
	private static final int	NO_PARENT_ASSIGNED	= -3;
	private static final int	UNVISITED			= -2;
	private static final int	VISITED				= -1;
	/**
	 * this is indexed into by node index and holds the total cost of the best
	 * path found so far to the given node. For example, costToThisNode[5] will
	 * hold the total cost of all the edges that comprise the best path to node
	 * 5 found so far in the search (if node 5 is present and has been visited
	 * of course).
	 */
	private float[]				costToThisNode;
	/** flag indicating that the target has been found. */
	private boolean				found;
	/** the graph being searched. */
	private HQCellGraph			graph;
	/**
	 * this is an indexed (by node) vector of "parent" edges leading to nodes
	 * connected to the SPT but that have not been added to the shortestPathTree
	 * yet.
	 */
	private WeightedGraphEdge[]	searchFrontier;
	/**
	 * the list of edges that comprise the shortest path tree - a directed
	 * sub-tree of the graph that encapsulates the best paths from every node on
	 * the SPT to the source node.
	 */
	private WeightedGraphEdge[]	shortestPathTree;
	/** the source node from where the search originates. */
	private int					source;
	/** the target node from where the search ends. */
	private int					target;
	private ArrayList<Integer> unsettled;
	private ArrayList<Integer> settled;
	/**
	 * Creates a new instance of {@link HQGraphSearchDijkstra}.
	 * @param graph
	 */
	public HQGraphSearchDijkstra(final HQCellGraph g) {
		graph = g;
		source = -1;
		target = -1;
		found = false;
		shortestPathTree = new WeightedGraphEdge[graph.getNumberOfNodes()];
		searchFrontier = new WeightedGraphEdge[graph.getNumberOfNodes()];
		costToThisNode = new float[graph.getNumberOfNodes()];
	}
	/**
	 * Gets the graph
	 * @return {@link SparseGraph}
	 */
	public HQCellGraph getGraph() {
		return graph;
	}
	/**
	 * Determines if the target node has been found.
	 * @return true if the target node has been found; false otherwise
	 */
	public boolean isFound() {
		return found;
	}
	/**
	 * returns the vector of edges defining the SPT. If a target is given
  //in the constructor, then this will be the SPT comprising all the nodes
  //examined before the target is found, else it will contain all the nodes
  //in the graph.

	 * @return
	 */
	public WeightedGraphEdge[] getAllPaths() {
		
	}
	int[] listOfPredecessors;
	public void search(final int src, final int targ) throws Exception {
		source = src;
		target = targ;
		DijkstraComparator comparator = new DijkstraComparator(this);
		// add source to list of unsettled vertices and immediately sort
		unsettled.add(source);
		Collections.sort(unsettled, comparator);
		// while the list of unsettled vertices still has nodes
		while (!unsettled.isEmpty()) {
			// get the node with the current shortest distance
			int nextClosestNode = unsettled.remove(0);
			// add next closest node to list of settled vertices
			settled.add(nextClosestNode);
			// relax the neighbors of next closest node. For each edge connected
			// to the next closest node
			WeightedGraphEdge[] edges = graph.getEdgesFromNode(nextClosestNode);
			for (int i = 0; i < edges.length; i++) {
				int v = edges[i].getTo();
				if (!settled.contains(v)) {
					float distToV = costToThisNode[v];
					float distToU = costToThisNode[nextClosestNode];
					if (distToV > distToU + edges[i].getCost()) {
						costToThisNode[v] = 
							(float) (distToU + edges[i].getCost());
						listOfPredecessors[v] = nextClosestNode;
						unsettled.add(v);
						Collections.sort(unsettled, comparator);
					}
				}
			}
			
		}
		// create an indexed priority queue that sorts smallest to largest
		// (front to back). Note that the maximum number of elements the iPQ
		// may contain is NumNodes(). This is because no node can be represented
		// on the queue more than once.
		IndexedPriorityQLow pq =
				new IndexedPriorityQLow(costToThisNode,
						graph.getNumberOfNodes());
		// put the source node on the queue
		pq.insert(source);

		// while the queue is not empty
		while (!pq.empty()) {
			// get the lowest cost node from the queue. Don't forget, the return
			// value is a *node index*, not the node itself. This node is the 
			// node not already on the SPT that is the closest to the source 
			// node
			int nextClosestNode = pq.pop();

			// move this edge from the search frontier to the shortest path tree
			shortestPathTree[nextClosestNode] = searchFrontier[nextClosestNode];

			// if the target has been found exit
			if (nextClosestNode == target) {
				return;
			}

			// now to relax the edges. For each edge connected to the next
			// closest node
			WeightedGraphEdge[] edges = graph.getEdgesFromNode(nextClosestNode);
			for (int i = 0; i < edges.length; i++) {
				// the total cost to the node this edge points to is the cost to
				// the current node plus the cost of the edge connecting them.
				float newCost = costToThisNode[nextClosestNode]
						+ (float) edges[i].getCost();

				// if this edge has never been on the frontier make a note of
				// the cost to reach the node it points to, then add the edge 
				// to the frontier and the destination node to the PQ.
				if (searchFrontier[edges[i].getTo()] == null) {
					costToThisNode[edges[i].getTo()] = newCost;
					pq.insert(edges[i].getTo());
					searchFrontier[edges[i].getTo()] = edges[i];
				} else if (newCost < costToThisNode[edges[i].getTo()]
						&& shortestPathTree[edges[i].getTo()] == null) {
					// else test to see if the cost to reach the destination
					// node via the current node is cheaper than the cheapest 
					// cost found so far. If this path is cheaper we assign 
					// the new cost to the destination node, update its entry 
					// in the PQ to reflect the change, and add the edge to 
					// the frontier
					costToThisNode[edges[i].getTo()] = newCost;
					// because the cost is less than it was previously, the PQ
					// must be resorted to account for this.
					pq.changePriority(edges[i].getTo());
					searchFrontier[edges[i].getTo()] = edges[i];
				}
			}
		}
	}
}
